class Solution1 {
public:
    //https://leetcode.cn/problems/sort-an-array/
    vector<int> sortArray(vector<int>& nums) 
    {
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void mergeSort(vector<int>& nums, int left, int right)
    {
        if(left == right) return ;
        int mid = left + (right - left)/2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid  + 1, right);
        vector<int> v(right - left + 1);//每一次递归都会创建该数组，浪费大量时间
        int l = left, r = mid + 1, j = 0;
        for(; l <= mid && r <= right;)
        {
            if(nums[l] < nums[r])
                v[j++] = nums[l++];
            else v[j++] = nums[r++];
        }
        while(l <= mid) v[j++] = nums[l++];
        while(r <= right) v[j++] = nums[r++];
        for(int i = left; i <= right; i++)
        {
            nums[i] = v[i - left];
        }
    }
};

class Solution1_1 {
    vector<int> v;//将该数组设在全局将节省了大量创建所损失的时间
public:
    vector<int> sortArray(vector<int>& nums) 
    {
        v.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void mergeSort(vector<int>& nums, int left, int right)
    {
        if(left == right) return ;
        int mid = left + (right - left)/2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid  + 1, right);
        int l = left, r = mid + 1, j = 0;
        for(; l <= mid && r <= right;)
        {
            if(nums[l] < nums[r])
                v[j++] = nums[l++];
            else v[j++] = nums[r++];
        }
        while(l <= mid) v[j++] = nums[l++];
        while(r <= right) v[j++] = nums[r++];
        for(int i = left; i <= right; i++)
        {
            nums[i] = v[i - left];
        }
    }
};


//https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
class Solution {
    vector<int> v;
public:
    int reversePairs(vector<int>& record) 
    {
        if(record.size() <= 1) return 0;
        v.resize(record.size());
        return mergeSort(record, 0, record.size() - 1);
    }

    int mergeSort(vector<int>& nums, int left, int right)
    {
        if(left == right) return 0;
        int mid = left + (right - left)/2;
        int count = 0;
        count = mergeSort(nums, left, mid) + mergeSort(nums, mid  + 1, right);
        int l = left, r = mid + 1, j = 0;
        for(; l <= mid && r <= right;)
        {
            if(nums[l] > nums[r])
            {
                count += mid - l + 1;
                v[j++] = nums[r++];
            }
            else
            {
                v[j++] = nums[l++];
            }
        }
        while(l <= mid) v[j++] = nums[l++];
        while(r <= right) v[j++] = nums[r++];
        for(int i = left; i <= right; i++)
        {
            nums[i] = v[i - left];
        }
        return count;
    }


};


//https://leetcode.cn/problems/count-of-smaller-numbers-after-self/
class Solution2 {
    vector<int> v;
    unordered_map<int,int> m;
    vector<int> v1;
    vector<int> v2;
public:
    vector<int> countSmaller(vector<int>& nums) 
    {
        v.resize(nums.size());
        v1.resize(nums.size());
        v2.resize(nums.size());
        int i = 0;  
        for(; i < nums.size(); i++)
        {
            m[i];
            v2[i] = i;
            v1[i] = i;
        }
        mergeSort(nums, 0, nums.size() - 1);
        i = 0;
        for(; i < v1.size(); i++)
        {
            v1[i] = m[i];
        }
        return v1;
    }

    void mergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right) return;
        int mid = left + (right - left)/2;
        mergeSort(nums, mid  + 1, right);
        mergeSort(nums, left, mid);
        int l = left, r = mid + 1, j = 0;
        for(; l <= mid && r <= right;)
        {
            if(nums[l] > nums[r])
            {
                v1[j] = v2[l];
                m[v2[l]] += right - r + 1;
                v[j++] = nums[l++];
            }
            else
            { 
                v1[j] = v2[r];
                v[j++] = nums[r++];
            }
        }
        while(l <= mid) 
        {
            v1[j] = v2[l];
            v[j++] = nums[l++];
        }
        while(r <= right) 
        {
            v1[j] = v2[r];
            v[j++] = nums[r++];
        }
        for(int i = left; i <= right; i++)
        {
            v2[i] = v1[i - left];
            nums[i] = v[i - left];
        }
    }
};

//优化版
class Solution2_1 {
    vector<int> v;
    int m[100000];
    vector<int> v1;
    vector<int> v2;
public:
    vector<int> countSmaller(vector<int>& nums) 
    {
        v1.resize(nums.size());
        v.resize(nums.size());
        v2.resize(nums.size());
        int i = 0;  
        for(; i < nums.size(); i++)
        {
            v2[i] = i;
            v1[i] = i;
        }
        mergeSort(nums, 0, nums.size() - 1);
        i = 0;
        for(; i < v1.size(); i++)
        {
            v1[i] = m[i];
        }
        return v1;
    }

    void mergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right) return;
        int mid = left + (right - left)/2;
        mergeSort(nums, mid  + 1, right);
        mergeSort(nums, left, mid);
        int l = left, r = mid + 1, j = 0;
        for(; l <= mid && r <= right;)
        {
            if(nums[l] > nums[r])
            {
                v1[j] = v2[l];
                m[v2[l]] += right - r + 1;
                v[j++] = nums[l++];
            }
            else
            { 
                v1[j] = v2[r];
                v[j++] = nums[r++];
            }
        }
        while(l <= mid) 
        {
            v1[j] = v2[l];
            v[j++] = nums[l++];
        }
        while(r <= right) 
        {
            v1[j] = v2[r];
            v[j++] = nums[r++];
        }
        for(int i = left; i <= right; i++)
        {
            v2[i] = v1[i - left];
            nums[i] = v[i - left];
        }
    }
};